import java.util.Stack;

public class SolutionInterview4_6 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return dfs(root,null,p);
    }

    private TreeNode dfs(TreeNode root, TreeNode p,TreeNode target) {
        if (root==target){
            if (root.right==null){
                return p;
            }else {
                TreeNode treeNode=root.right;
                while (treeNode.left!=null){
                    treeNode=treeNode.left;
                }
                return treeNode;
            }
        }
        if (root.val>target.val){
            return dfs(root.left,root,target);
        }else {
            return dfs(root.right,p,target);
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(1);
        TreeNode t=new TreeNode(2,treeNode,new TreeNode(3));
        System.out.println(new SolutionInterview4_6().inorderSuccessor(t,treeNode).val);
    }
}
